#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=5000;
int f[maxn],m[maxn][maxn];
int c,n;
int min(int x,int y){return x<y?x:y;}
int main()
{
	while(scanf("%d%d",&c,&n)!=EOF)
	{
		for(int i=1;i<=n;i++)
			for(int j=i;j<=n;j++)
				scanf("%d",&m[i][j]);
		f[0]=0;
		for(int i=1;i<=n;i++)
		{
			f[i]=0x3f3f3f3f;
			for(int k=0;k<=i-1;k++)
				f[i]=min(f[i],f[k]+c+m[k+1][i]);
		}
		printf("%d\n",f[n]);
	}
	return 0;
}

